// https://www.lintcode.com/problem/kth-smallest-sum-in-two-sorted-arrays/description
// 其实和matrix那题一样的，而且加起来也可以构造那样的matrix
// 两个排序数组可以转换为排序矩阵

class Solution {
public:
    /**
     * @param A: an integer arrays sorted in ascending order
     * @param B: an integer arrays sorted in ascending order
     * @param k: An integer
     * @return: An integer
     */
    int kthSmallestSum(vector<int> &A, vector<int> &B, int k) {
        if (A.empty() || B.empty())
            return -1;
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, 
            greater<tuple<int, int, int>>> q;
        q.emplace(A[0] + B[0], 0, 0);
        int n = A.size();
        int m = B.size();
        int i = 0;
        int j = 0;
        vector<vector<bool>> visited(n, vector<bool>(m, false)); //或者可以用map来记
        visited[0][0] = true;
        int ans = -1;
        for (int i = 0; i < k; ++i)
        {
            int val, x, y;
            tie(val, x, y) = q.top();
            // visited[x][y] = true;
            q.pop();
            ans = val;
            cout << val << " " << x << " " << y << endl;
            if (x + 1 < A.size() && !visited[x + 1][y]) 
            {
                q.emplace(A[x + 1] + B[y], x + 1, y); //注意边界
                visited[x + 1][y] = true; //visited要在这边加
            }
            if (y + 1 < B.size() && !visited[x][y + 1]) 
            {
                q.emplace(A[x] + B[y + 1], x, y + 1);
                visited[x][y + 1] = true;
            }
        }
        // return get<0>(q.top());
        return ans;
    }
};